import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class BestFirst
{

	/*
	 * Integration instructions (obviously, adapt to any changes you make to existing code) 1. initialize a SearchGrid() with an array of Strings, where each String represents a row, top to bottom (just like the original input) 2. call BestFirst.pathFind(grid, end); (grid from step 1) 3. if I missed something, fix it. if there are bugs, I apologize and wish you luck debugging -_-
	 */

	public static void main(String[] args)
	{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		List<String> raw = new ArrayList<String>();
		try
		{
			String s;
			while ((s = in.readLine()) != null)
				raw.add(s);
		} catch (IOException e)
		{
			e.printStackTrace();
		}
		SearchGrid grid = new SearchGrid(raw.toArray(new String[0]));
//		Location end = new Location(Integer.parseInt(args[0]), Integer.parseInt(args[1]));
		Location end = new Location(27, 22);
		long time = -System.nanoTime();
		System.out.println(BestFirst.pathFind(grid, end));
		time += System.nanoTime();
		System.out.println(time);
	}

	/**
	 *
	 * @param grid
	 * @param end
	 * @return String of directions, or null if unreachable
	 */
	public static String pathFind(SearchGrid grid, Location end)
	{
		Set<Long> closedSet = new HashSet<Long>();
		Comparator<SearchNode> comparator = new Comparator<SearchNode>()
		{
			@Override
			public int compare(SearchNode arg0, SearchNode arg1)
			{
				int temp = arg0.f() - arg1.f();
				if (temp != 0)
					return temp;
				return arg0.getHeuristic() - arg1.getHeuristic();
			}
		};
		BinaryHeap<SearchNode> openHeap = new BinaryHeap<SearchNode>(comparator);

		SearchNode start = new SearchNode(grid);
		openHeap.addHeap(start);

		while (true)
		{
			// step 1
			SearchNode current;
			try
			{
				current = openHeap.popRoot();
			} catch (ArrayIndexOutOfBoundsException e)
			{
				break;
			}
			closedSet.add(current.getGrid().longHashCode());

			// step 2
			if (current.getGrid().getRobo().equals(end))
			{
				return current.getPath();
			}

			// step 3
			List<SearchNode> neighbors = current.getNeighbors();
			current.setGridNull(); //allow garbage collection of grid as node may still be referenced by children

			// step 4
			for (int i = 0; i < neighbors.size(); i++)
			{
				SearchNode neighbor = neighbors.get(i);
				SearchNode openObj = openHeap.find(neighbor);
				if (!closedSet.contains(neighbor.getGrid().longHashCode()) && openObj == null) // step 4a
				{
					neighbor.calculateHeuristic(end);
					openHeap.addHeap(neighbor);
				} else if (openObj != null) //should always be if heuristic is monotonic
				{
					Move currentToNeighbor = neighbor.getMoveFromParent();
					neighbor = openObj;
					if (current.getDistSoFar() + 1 < neighbor.getDistSoFar())
					{ // step 4b
						neighbor.setParent(current);
						neighbor.setMoveFromParent(currentToNeighbor);
						neighbor.setDistSoFar(current.getDistSoFar() + 1);
						if (openObj != null) // force resort
						{
							openHeap.update(neighbor);
						}
					}
				}
			}
		}
		return null;
	}
}
